package tuhu.q3;

public class RoadPlanning {
    // 并查集的find操作
    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 并查集的union操作
    private void union(int[] parent, int[] rank, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    public int roadPlan(int cityNumber, int roadNumber, int[][] roadArray) {

        int[] parent = new int[cityNumber];
        int[] rank = new int[cityNumber];


        for (int i = 0; i < cityNumber; i++) {
            parent[i] = i;
            rank[i] = 0;
        }


        for (int[] road : roadArray) {
            int city1 = road[0];
            int city2 = road[1];
            union(parent, rank, city1, city2);
        }


        int components = 0;
        for (int i = 0; i < cityNumber; i++) {
            if (find(parent, i) == i) {
                components++;
            }
        }


        return components - 1;
    }

    // 测试主函数
    public static void main(String[] args) {
        RoadPlanning solution = new RoadPlanning();

        // 测试输入
        int cityNumber = 20;
        int roadNumber = 7;
        int[][] roadArray = {{0, 1}, {6, 9}, {3, 8}, {5, 11}, {2, 12}, {6, 10}, {4, 8}};

        // 计算需要建造的最少道路数量
        int result = solution.roadPlan(cityNumber, roadNumber, roadArray);
        System.out.println("需要建造的最少道路数量: " + result); // 应输出 12
    }
}
